package tech.aistar.util;

import java.util.Arrays;

/**
 * 本类用来演示: 数组排序
 *
 * @author: success
 * @date: 2021/3/11 1:33 下午
 */
public class ArraySortUtil {
    public static void main(String[] args) {
        //int[] arr ={5,-3,-1,3,1,7,5,2,1};
        //bubble(arr);

        //directlyInsert(arr);

        //selectSort(arr);

        //quickSort(arr,0,arr.length-1);

        int[] arr = {1,2,3,5,5,6,7,8};
        System.out.println(binarySearch(arr,5));
    }

    /**
     * 冒泡排序 - 从小到大
     * @param arr
     * @return
     */
    public static int[] bubble(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    //交换数据
                    int t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = t;
                }
            }
        }
        return arr;
    }

    /**
     * 直接插入 - 了解 - 最简单
     * @param arr
     * @return
     */
    public static int[] directlyInsert(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 ; j--) {
                if(arr[j] < arr[j-1]){
                    int t = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = t;
                }
            }
        }
        return arr;
    }

    /**
     * 选择排序
     * @param arr
     * @return
     */
    public static int[] selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if(arr[i]>arr[j]){
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
        }
        return arr;
    }

    /**
     * 快速排序
     * **挖坑填数**
     *
     * 1. **将基准数挖出形成第一个坑**
     * 2. **由后向前找比它小的数,找到后挖出此数填到前一个坑中**
     * 3. **由前向后找比它大或等于的数,找到后也挖出此数填到前一个坑中**
     * 4. **再重复执行2,3两步骤.例如对5391672408**
     */
    public static void quickSort(int[] arr,int start,int end){
        //判断
        if(start<end){
            //1. 找到基准数的应该存放的索引 - start和end交汇
            int index = getBaseInex(arr,start,end);
            quickSort(arr,0,index-1);
            quickSort(arr,index+1,end);
        }
    }

    /**
     * 为了找start和end重叠的位置
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private static int getBaseInex(int[] arr, int start, int end) {
        int i = start; // 从左到右移动的下标
        int j = end; // 从右到左移动的下标
        //确定基准数
        int x = arr[i];

        while(i<j){
            //由后向前找比它小的数,找到后挖出此数填到前一个坑中
            while(i<j && arr[j]>=x){
                j--;
            }
            //arr[j] - 比x要小的数
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            //由前向后找比它大或等于的数,找到后也挖出此数填到前一个坑中
            while(i<j && arr[i]<x){
                i++;
            }
            //arr[i]>=x
            if(i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        //i和j开始交汇了...
        arr[i] = x;//基准数放入到第一次重合的位置
        return i;
    }

    /**
     * 二分搜索法
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch(int[] arr,int target){
        int startIndex = 0;
        int endIndex = arr.length-1;

        while(startIndex<=endIndex){
            //算出中间索引 - (startIndex + endIndex)/2
            int centerIndex = (startIndex + endIndex)>>>1;
            if(target == arr[centerIndex])
                return centerIndex;
            else if(target>arr[centerIndex])
                startIndex = centerIndex+1;
            else
                endIndex = centerIndex-1;
        }
        return -1;
    }
}
